package 华为OD机试B卷复用题.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HJ42_机器人走迷宫 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试B卷复用题/进阶题/input/42.txt"));
        MyUtil.START();
        Solution(in);
        MyUtil.END();
    }

    static int row, cloumn;
    static int[][] matrix; // 0 未处理，1 墙壁，2 可达，-1 陷阱。

    static void Solution(Scanner in) {
        row = in.nextInt();
        cloumn = in.nextInt();
        matrix = new int[row][cloumn];
        int N = in.nextInt();
        for (int i = 0; i < N; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            matrix[x][y] = 1;
        }
        matrix[row - 1][cloumn - 1] = 2;
        dfs(0, 0);
        // 遍历矩阵，统计相关数据，输出
    }

    static boolean dfs(int x, int y) {
        if (x < 0 || x >= row || y < 0 || y >= cloumn) {
            return false;
        }
        // 与当前值无关，判断下面的节点去
        //        if (matrix[x][y] == 1 || matrix[x][y] == -1) {
        //            return false;
        //        }
        //        if (matrix[x][y] == 2) {
        //            return true;
        //        }
        if (matrix[x][y] == 0) {
            boolean xNext = dfs(x + 1, y);
            boolean yNext = dfs(x, y + 1);
            if (xNext || yNext) {
                matrix[x][y] = 2;
            } else {
                matrix[x][y] = -1;
            }
        }
        return matrix[x][y] == 2;
    }
}
